import java.util.ArrayList;
import java.util.Deque;
import java.util.LinkedList;
import java.util.Stack;

public class Solution {
    //JZ9 用两个栈实现队列
    Stack<Integer> stack1 = new Stack<Integer>();
    Stack<Integer> stack2 = new Stack<Integer>();

 /*   public void push(int node) {
        if(stack2.isEmpty()){
            stack1.push(node);
        }else{
            while(!stack2.isEmpty()){
                stack1.push(stack2.pop());
            }
            stack1.push(node);
        }
    }

    public int pop() {
        int ret = 0;
        if(!stack2.isEmpty()){
            ret = stack2.pop();
        }else{
            while(!stack1.isEmpty()){
                stack2.push(stack1.pop());
            }
            ret = stack2.pop();
        }
        return ret;
    }*/
    //JZ30 包含min函数的栈
    Stack<Integer> stack = new Stack<>();
    Stack<Integer> minStack = new Stack<>();
    public void push(int node) {
        //最小栈为空直接放数据
        if(minStack.isEmpty()){
            minStack.push(node);
        }else if(minStack.peek() >= node){//小于等于最小栈栈顶元素都要放入
            minStack.push(node);
        }
        //主栈必须放
        stack.push(node);
    }

    public void pop() {
        //检测主栈元素是否等于最小栈栈顶元素，若等于也需要pop
        //这里要注意pop和peek操作返回的都是泛型类，没有整数比较时需要强制类型转化
        if((int)stack.pop() == (int)minStack.peek()){
            minStack.pop();
        }
    }

    public int top() {
        return stack.peek();
    }

    public int min() {
        return minStack.peek();
    }
    //JZ31栈的压入、弹出序列
    public boolean IsPopOrder(int [] pushA,int [] popA) {
        Stack<Integer> stack = new Stack<>();
        int count = 0;//计数：与压栈数据匹配则加一
        for(int i = 0; i < pushA.length; i++){
            if(pushA[i] == popA[count]){
                //先压栈，再判断
                stack.push(pushA[i]);
                while(stack.peek() == popA[count]){
                    stack.pop();
                    count++;
                    //popA遍历完说明正确
                    if(count == pushA.length){
                        return true;
                    }
                    /**
                     *弹出栈后，可能一个元素也不剩，这时再到while里判断，
                     *有可能能造成对空指针的解引用操作
                     */
                    if(stack.empty()){
                        break;
                    }
                }
            }
            else{
                stack.push(pushA[i]);
            }
        }
        return false;
    }
    //JZ73 翻转单词序列
    public String ReverseSentence(String str) {
        Stack<String> stack = new Stack<>();
        //每个单词用空格分开
        String[] strArr = str.split(" ");
        StringBuilder ret = new StringBuilder();
        //压栈
        for(int i = 0; i < strArr.length; i++){
            //注意空格隔开
            if(i != 0){
                stack.push(" ");
            }
            stack.push(strArr[i]);
        }
        //出栈
        while(!stack.isEmpty()){
            ret.append(stack.pop());
        }
        return ret.toString();
    }
    //JZ59 滑动窗口的最大值（不行，时间复杂度O(n^2)）
    public ArrayList<Integer> maxInWindows(int [] num, int size) {
        ArrayList<Integer> array = new ArrayList<>();
        //假定最大值
        for(int i = 0; i < num.length - size + 1; i++){
            int left = i;
            int right = left + size - 1;
            //求最大值
            int max = num[left];//假定最大值
            for(int j = left; j <= right; j++){
                if(num[j] > max){
                    max = num[j];
                }
            }
            array.add(max);
        }
        return array;
    }
    //JZ59 滑动窗口的最大值(双端队列优化)
    public static ArrayList<Integer> maxInWindows(int [] num, int size){
        ArrayList<Integer> array = new ArrayList<>();
        //长度为零直接返回空表
        if(size == 0) {
            return array;
        }
        int begin = 0;
        //双端队列用来存放下标
        Deque<Integer> deque = new LinkedList<>();
        for(int i = 0; i < num.length; i++){
            //制造虚拟滑动窗口起点
            begin = i - size + 1;
            //若为空，先放入元素假定为最大值
            if(deque.isEmpty()){
                deque.add(i);
            }
            else if(begin > deque.peekFirst()){
                deque.pollFirst();
            }
            //队尾开始比较，把比他小的都出队
            while((!deque.isEmpty()) && num[deque.peekLast()] <= num[i]){
                deque.pollLast();
            }
            deque.add(i);
            if(begin >= 0){
                array.add(num[deque.peekFirst()]);
            }
        }
        return array;
    }
}
